{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Hanota LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: hanota"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #汉诺塔问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:<br>\n",
    "(1) 每次只能移动一个盘子;<br>\n",
    "(2) 盘子只能从柱子顶端滑出移到下一根柱子;<br>\n",
    "(3) 盘子只能叠在比它大的盘子上。</p>\n",
    "\n",
    "<p>请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。</p>\n",
    "\n",
    "<p>你需要原地修改栈。</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：A = [2, 1, 0], B = [], C = []\n",
    "<strong> 输出</strong>：C = [2, 1, 0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例2:</strong></p>\n",
    "\n",
    "<pre><strong> 输入</strong>：A = [1, 0], B = [], C = []\n",
    "<strong> 输出</strong>：C = [1, 0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>A中盘子的数目不大于14个。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [hanota-lcci](https://leetcode.cn/problems/hanota-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [hanota-lcci](https://leetcode.cn/problems/hanota-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    # 定义move 函数移动汉诺塔\n",
    "    def move(self,n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return \n",
    "        else:\n",
    "            self.move(n-1, A, C, B)  # 将A上面n-1个通过C移到B\n",
    "            C.append(A[-1])          # 将A最后一个移到C\n",
    "            A.pop()                  # 这时，A空了\n",
    "            self.move(n-1,B, A, C)   # 将B上面n-1个通过空的A移到C\n",
    "\n",
    "# 作者：腐烂的橘子\n",
    "# 链接：https://leetcode.cn/problems/hanota-lcci/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        C += A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    def move(self, n, A, B, C):\n",
    "        if n == 0: return \n",
    "        B = A[1:]\n",
    "        C.append(A[0])\n",
    "        print(C)\n",
    "        self.move(n-1, B, A, C)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        for i in A:\n",
    "            C.append(i)\n",
    "        A.clear()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    # 定义move 函数移动汉诺塔\n",
    "    def move(self,n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return \n",
    "        else:\n",
    "            self.move(n-1, A, C, B)  # 将A上面n-1个通过C移到B\n",
    "            C.append(A[-1])          # 将A最后一个移到C\n",
    "            A.pop()                  # 这时，A空了\n",
    "            self.move(n-1,B, A, C)   # 将B上面n-1个通过空的A移到C\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def move(n,A,B,C):\n",
    "            if n==1:\n",
    "                C.append(A.pop())\n",
    "                return \n",
    "            \n",
    "            move(n-1,A,C,B)\n",
    "            move(1,A,B,C)\n",
    "            move(n-1,B,A,C)\n",
    "        \n",
    "        n = len(A)\n",
    "        move(n,A,B,C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        self.move(len(A), A, B, C)\n",
    "        \n",
    "    def move(self, n: int, src: List[int], tmp: List[int], dst: List[int]) -> None:\n",
    "        if n <= 0:\n",
    "            return\n",
    "        self.move(n - 1, src, dst, tmp)\n",
    "        val = src.pop(len(src) - 1)\n",
    "        dst.append(val)\n",
    "        self.move(n - 1, tmp, src, dst)\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(A)\n",
    "        self.move(n,A,B,C)\n",
    "    def move(self,n,A,B,C):\n",
    "\n",
    "        if n==1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return \n",
    "        self.move(n-1,A,C,B)\n",
    "        C.append(A[-1])\n",
    "        A.pop()\n",
    "        self.move(n-1,B,A,C)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        for i in A:\n",
    "            C.append(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        for i in A:\n",
    "            B.append(i)\n",
    "        for i in B:\n",
    "            C.append(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def move(self, size: int, start: List[int], intern: List[int], end: List[int]):\n",
    "        if size == 1:\n",
    "            end.append(start[-1])\n",
    "            start.pop()\n",
    "            return\n",
    "        self.move(size - 1, start, end, intern)\n",
    "        end.append(start[-1])\n",
    "        start.pop()\n",
    "        self.move(size - 1, intern, start, end)\n",
    "\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        self.move(len(A), A, B, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        n=len(A)\n",
    "        self.move(n,A,B,C)\n",
    "    def move(self,n,A,B,C):\n",
    "        if n==1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return\n",
    "        else:\n",
    "            self.move(n-1,A,C,B)\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            self.move(n-1,B,A,C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        C.extend(A)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "\n",
    "    def move(self, n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A.pop())\n",
    "            return\n",
    "        else:\n",
    "            self.move(n - 1, A, C, B)\n",
    "            C.append(A.pop())\n",
    "            self.move(n - 1, B, A, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def dfs(n, A, B, C):\n",
    "            if n==1:\n",
    "                C.append(A[-1])\n",
    "                A.pop()\n",
    "                return \n",
    "            else:\n",
    "                dfs(n-1, A, C, B)\n",
    "                C.append(A[-1])\n",
    "                A.pop()\n",
    "                dfs(n-1, B, A, C)\n",
    "        n = len(A)\n",
    "        dfs(n, A, B, C)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def hanoi(n, source, auxiliary, target):\n",
    "            if n == 1:\n",
    "                target.append(source.pop())\n",
    "            else:\n",
    "                # 将 n-1 个盘子从 source 移动到 auxiliary\n",
    "                hanoi(n - 1, source, target, auxiliary)\n",
    "                # 将第 n 个盘子从 source 移动到 target\n",
    "                target.append(source.pop())\n",
    "                # 再将 n-1 个盘子从 auxiliary 移动到 target\n",
    "                hanoi(n - 1, auxiliary, source, target)\n",
    "\n",
    "        n = len(A)\n",
    "        hanoi(n, A, B, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        C += A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def hanoi(n: int , A: List[int], B: List[int], C: List[int]) -> None:\n",
    "            if n == 1:\n",
    "                C.append(A.pop())\n",
    "            else:\n",
    "                hanoi(n - 1, A, C, B)  # 将n-1个盘从A->B，借助C\n",
    "                C.append(A.pop())\n",
    "                hanoi(n - 1, B, A, C)  # 将n-1个盘从B->C，借助A\n",
    "        hanoi(len(A), A, B, C)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        self.helper(A, B, C, len(A))\n",
    "        \n",
    "    def helper(self, A, B, C, n):\n",
    "        if n == 1:\n",
    "            C.append(A.pop())\n",
    "            return\n",
    "        # 上面的n-1个 通过C放到B\n",
    "        self.helper(A, C, B, n-1)\n",
    "        # 将A的最后一个放在C\n",
    "        C.append(A.pop())\n",
    "        self.helper(B, A, C, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\" \n",
    "        n = len(A)\n",
    "        def func(A,B,C,n):\n",
    "            if n==1:\n",
    "                C.append(A.pop())\n",
    "                return\n",
    "            else:\n",
    "                func(A,C,B,n-1)\n",
    "                C.append(A.pop())\n",
    "                func(B,A,C,n-1)\n",
    "        func(A,B,C,n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def move(n, A, B, C) -> None:\n",
    "            if n == 1:\n",
    "                C.append(A.pop())\n",
    "                return \n",
    "            \n",
    "            move(n-1, A, C, B)\n",
    "            C.append(A.pop())\n",
    "            move(n-1, B, A, C)\n",
    "    \n",
    "        move(len(A), A, B, C)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        C.extend(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "\n",
    "    def move(self, n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A.pop())\n",
    "        else:\n",
    "            self.move(n - 1, A, C, B)\n",
    "            C.append(A.pop())\n",
    "            self.move(n - 1, B, A, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        for i in A:\n",
    "            C.append(i) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        if n == 1 :\n",
    "            C.append(A[0])\n",
    "            A.pop()\n",
    "            return\n",
    "        B.extend(A[1:])\n",
    "        C.append(A[0])\n",
    "        A.clear()\n",
    "        self.hanota(B,A,C)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def move(src, dst):\n",
    "            dst.append(src.pop())\n",
    "\n",
    "        def dfs(src, buf, dst, n):\n",
    "            if n == 1:\n",
    "                move(src, dst)\n",
    "                return\n",
    "            dfs(src, dst, buf, n - 1)\n",
    "            move(src, dst)\n",
    "            dfs(buf, src, dst, n - 1)\n",
    "\n",
    "        dfs(A, B, C, len(A))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def move(self,n,A,B,C):\n",
    "        if n == 1:\n",
    "            C.append(A.pop())\n",
    "            return\n",
    "        self.move(n-1, A,C,B)\n",
    "        C.append(A.pop())\n",
    "        self.move(n-1,B,A,C)\n",
    "\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        self.move(len(A),A,B,C)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.move(n,A,B,C)\n",
    "\n",
    "    def move(self,n,A,B,C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "        else:\n",
    "            self.move(n-1,A,C,B)\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            self.move(n-1,B,A,C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        C.extend(A+B)\n",
    "        return(sorted(C))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        all_list = [A, B, C]\n",
    "        total_len = len(A) - 1\n",
    "        self.hanoi(total_len, all_list, True)\n",
    "    \n",
    "    def hanoi(self, total_len, all_list, left):\n",
    "        if total_len < 0:\n",
    "            return\n",
    "        \n",
    "        self.hanoi(total_len-1, all_list, not left)\n",
    "\n",
    "        # find the 'total_len' plate\n",
    "        if len(all_list[0]) and all_list[0][-1] == total_len:\n",
    "            tower_num = 0\n",
    "        elif len(all_list[1]) and all_list[1][-1] == total_len:\n",
    "            tower_num = 1\n",
    "        else:\n",
    "            tower_num = 2\n",
    "\n",
    "        # move\n",
    "        if left:\n",
    "            all_list[(tower_num-1) % len(all_list)].append(all_list[tower_num].pop())\n",
    "        else:\n",
    "            all_list[(tower_num+1) % len(all_list)].append(all_list[tower_num].pop())\n",
    "        \n",
    "        self.hanoi(total_len-1, all_list, not left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def move(src, tar):\n",
    "            pan = src.pop()\n",
    "            tar.append(pan)\n",
    "\n",
    "        def recurr(n, src, tar, buf):\n",
    "            if n > 1:\n",
    "                recurr(n - 1, src, buf, tar)\n",
    "                recurr(1, src, tar, buf)\n",
    "                recurr(n - 1, buf, tar, src)\n",
    "            else:\n",
    "                move(src, tar)\n",
    "\n",
    "        recurr(len(A), A, C, B)\n",
    "        return C "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    def move(self, n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return\n",
    "        else:\n",
    "            self.move(n-1, A, C, B)\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            self.move(n-1, B, A, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "\n",
    "        def dfs(n, A, B, C):\n",
    "            if n == 1:\n",
    "                C.append(A.pop())\n",
    "                return \n",
    "\n",
    "            dfs(n-1, A, C, B)\n",
    "            C.append(A.pop())\n",
    "            dfs(n-1, B, A, C)\n",
    "\n",
    "\n",
    "        return dfs(n, A, B, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        self.move(len(A),A,B,C)\n",
    "\n",
    "    def move(self, len, From, Through, To):\n",
    "        if len==1:\n",
    "            To.append(From[-1])\n",
    "            From.pop()\n",
    "        else:\n",
    "            self.move(len-1,From,To,Through)\n",
    "            self.move(1,From,Through,To)\n",
    "            self.move(len-1,Through,From,To)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    def move(self,n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return \n",
    "        else:\n",
    "            self.move(n-1, A, C, B)  \n",
    "            C.append(A[-1])         \n",
    "            A.pop()                 \n",
    "            self.move(n-1,B, A, C)  \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    # 定义move 函数移动汉诺塔\n",
    "    def move(self,n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return \n",
    "        else:\n",
    "            self.move(n-1, A, C, B)  # 将A上面n-1个通过C移到B\n",
    "            C.append(A[-1])          # 将A最后一个移到C\n",
    "            A.pop()                  # 这时，A空了\n",
    "            self.move(n-1,B, A, C)   # 将B上面n-1个通过空的A移到C\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def move(n,A,B,C):\n",
    "            if n == 1:\n",
    "                C.append(A.pop())\n",
    "                return\n",
    "            else:\n",
    "                move(n-1,A,C,B)\n",
    "                C.append(A.pop())\n",
    "                move(n-1,B,A,C)\n",
    "        n = len(A)\n",
    "        move(n,A,B,C)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        for i in range(0,len(A)):\n",
    "            C.append(A[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    # 定义move 函数移动汉诺塔\n",
    "    def move(self,n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return \n",
    "        else:\n",
    "            self.move(n-1, A, C, B)  # 将A上面n-1个通过C移到B\n",
    "            C.append(A[-1])          # 将A最后一个移到C\n",
    "            A.pop()                  # 这时，A空了\n",
    "            self.move(n-1,B, A, C)   # 将B上面n-1个通过空的A移到C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        C += A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def f(num,s,e,o):\n",
    "            if num==1:\n",
    "                e.append(s.pop())\n",
    "            elif num==2:\n",
    "                f(1,s,o,e)\n",
    "                f(1,s,e,0)\n",
    "                f(1,o,e,s)\n",
    "            else:\n",
    "                f(num-1,s,o,e)\n",
    "                f(1,s,e,o)\n",
    "                f(num-1,o,e,s)\n",
    "        f(len(A),A,C,B)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        C += A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        def move(n,A,B,C):\n",
    "            if n==1:\n",
    "                C.append(A.pop())\n",
    "                return\n",
    "            else:\n",
    "                move(n-1,A,C,B)\n",
    "                C.append(A.pop())\n",
    "                move(n-1,B,A,C)\n",
    "        move(n,A,B,C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.moving(n, A, B, C)\n",
    "\n",
    "    def moving(self, n, A, B, C):\n",
    "        if n > 0:\n",
    "            self.moving(n-1, A, C, B)\n",
    "            C.append(A.pop())\n",
    "            self.moving(n-1, B, A, C)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        #递归\n",
    "        #初始为a，b为空，终点为c\n",
    "        n=len(A)\n",
    "        a,b,c=A,B,C\n",
    "        def move(n,a,b,c):\n",
    "            if n==1:\n",
    "                c.append(a[-1])#将a中最后一个移动到c\n",
    "                a.pop()\n",
    "                return\n",
    "            move(n-1,a,c,b)#先将a最上面的n-1个，从a，经过c的帮助，移动到b\n",
    "            c.append(a[-1])#将a中最大的移动到c\n",
    "            a.pop()#a中最后一个弹出，a变为空\n",
    "            move(n-1,b,a,c)#前面n-1个已经移动到b了，a为空,b上面有n-1个，因此将b上的n-1个，通过空的a的帮助，移动到c\n",
    "        move(n,a,b,c)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        n=len(A)\n",
    "        for i in range(n//2):\n",
    "            temp=A[i]\n",
    "            A[i]=A[n-1-i]\n",
    "            A[n-1-i]=temp\n",
    "        for i in range(n):\n",
    "            C.append(A.pop())\n",
    "    # 定义move 函数移动汉诺塔\n",
    "    # def move(self,n, A, B, C):\n",
    "    #     if n == 1:\n",
    "    #         C.append(A.pop())\n",
    "    #         return \n",
    "    #     else:\n",
    "    #         self.move(n-1, A, C, B)  \n",
    "    #         C.append(A.pop())                          \n",
    "    #         self.move(n-1,B, A, C)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    \n",
    "\n",
    "    def move(self, n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A.pop())\n",
    "        else:\n",
    "            self.move(n-1, A, C, B)\n",
    "            C.append(A.pop())\n",
    "            self.move(n-1, B, A, C)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def hanoi(n,x,y,z):\n",
    "            if n == 1:\n",
    "                z.append(x.pop())\n",
    "                return\n",
    "            else:\n",
    "                hanoi(n-1,x,z,y)\n",
    "                hanoi(1,x,y,z)\n",
    "                hanoi(n-1,y,x,z)\n",
    "                \n",
    "        hanoi(len(A),A,B,C)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    def move(self, n , A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return\n",
    "        else:\n",
    "            self.move(n-1, A, C, B)\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            self.move(n-1, B, A, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(A)\n",
    "        self.move(n,A,B,C)\n",
    "\n",
    "    def move(self,n,A,B,C):\n",
    "        if n==1:\n",
    "            C.append(A.pop())\n",
    "        else:\n",
    "            self.move(n-1,A,C,B)#C当媒介,A移动到B\n",
    "            C.append(A.pop())\n",
    "            self.move(n-1,B,A,C)#A当媒介，B移到C\n",
    "\n",
    "if __name__==\"__main__\":\n",
    "    A=[2, 1, 0]\n",
    "    B=[]\n",
    "    C=[]\n",
    "    s=Solution()\n",
    "    print(s.hanota(A,B,C))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        n = len(A)\n",
    "        self.m(n, A, B, C)\n",
    "    def m(self,n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A.pop(-1))\n",
    "            return\n",
    "        self.m(n-1, A, C, B)  \n",
    "        C.append(A.pop(-1))          \n",
    "        self.m(n-1,B, A, C)\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        for i in A:\n",
    "            C.append(i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        C.extend(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "\n",
    "    def move(self, n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "        else:\n",
    "            self.move(n-1, A, C, B)\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            self.move(n-1, B, A, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(A)\n",
    "        def move(n,A,B,C):\n",
    "            if n==1:\n",
    "                C.append(A[-1])\n",
    "                A.pop()\n",
    "            else:\n",
    "                move(n-1,A,C,B)\n",
    "                C.append(A[-1])\n",
    "                A.pop()\n",
    "                move(n-1,B,A,C)\n",
    "        move(n,A,B,C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        if len(A) > 0:\n",
    "            i = 0\n",
    "            t = len(A)\n",
    "            while i < t - 1:\n",
    "                B.append(A.pop(0))\n",
    "                i += 1\n",
    "            C.insert(0, A.pop(0))\n",
    "            self.hanota(B, A, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    # 定义move 函数移动汉诺塔\n",
    "    def move(self,n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return \n",
    "        else:\n",
    "            self.move(n-1, A, C, B)  # 将A上面n-1个通过C移到B\n",
    "            C.append(A[-1])          # 将A最后一个移到C\n",
    "            A.pop()                  # 这时，A空了\n",
    "            self.move(n-1,B, A, C)   # 将B上面n-1个通过空的A移到C\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        def move(n,A,B,C):\n",
    "            if n == 1:\n",
    "                C.append(A.pop())\n",
    "            else:\n",
    "                move(n-1,A,C,B)\n",
    "                C.append(A.pop())\n",
    "                move(n-1,B,A,C)\n",
    "            \n",
    "        move(len(A),A,B,C)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        length = len(A)\n",
    "        def move(n, fr, spare, to):\n",
    "            if n == 1:\n",
    "                to.append(fr[0])\n",
    "                fr.pop(0)\n",
    "                return to.sort(reverse = True)\n",
    "            else:\n",
    "                move(n-1, fr, to, spare)\n",
    "                move(1, fr, spare, to)\n",
    "                move(n-1, spare, fr, to)\n",
    "        move(length, A, B, C)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        def move(n, A, B, C):\n",
    "            if n == 1:\n",
    "                C.append(A.pop())\n",
    "                return\n",
    "            else:\n",
    "                move(n - 1, A, C, B)\n",
    "                C.append(A.pop())\n",
    "                move(n - 1, B, A, C)\n",
    "        move(n, A, B, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        C += A\n",
    "        A = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    # 定义move 函数移动汉诺塔\n",
    "    def move(self,n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return \n",
    "        else:\n",
    "            self.move(n-1, A, C, B)  # 将A上面n-1个通过C移到B\n",
    "            C.append(A[-1])          # 将A最后一个移到C\n",
    "            A.pop()                  # 这时，A空了\n",
    "            self.move(n-1,B, A, C)   # 将B上面n-1个通过空的A移到C\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    # 定义move 函数移动汉诺塔\n",
    "    def move(self,n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return \n",
    "        else:\n",
    "            self.move(n-1, A, C, B)  \n",
    "            C.append(A[-1])          \n",
    "            A.pop()                \n",
    "            self.move(n-1,B, A, C)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def hanoi(n, A, B, C):\n",
    "            if n == 1:\n",
    "                C.append(A[-1])\n",
    "                A.pop()\n",
    "            else:\n",
    "                hanoi(n-1, A, C, B)\n",
    "                C.append(A[-1])\n",
    "                A.pop()\n",
    "                hanoi(n-1, B, A, C)\n",
    "        n = len(A)\n",
    "        hanoi(n, A, B, C)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.move(n, A, B, C)\n",
    "    \n",
    "    def move(self, n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            return\n",
    "        else:\n",
    "            self.move(n-1, A, C, B)\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            self.move(n-1, B, A, C)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def move(n: int, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "            if n == 1:\n",
    "                C.append(A.pop())\n",
    "                return\n",
    "            \n",
    "            move(n - 1, A, C, B)\n",
    "            C.append(A.pop())\n",
    "            move(n - 1, B, A, C)\n",
    "        \n",
    "        n = len(A)\n",
    "        move(n, A, B, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        self.move(n, A,B,C)\n",
    "\n",
    "    def move(self, n, A, B, C):\n",
    "        if n == 1:\n",
    "            C.append(A.pop())\n",
    "        else:\n",
    "            self.move(n-1, A,C,B)\n",
    "            C.append(A.pop())\n",
    "            self.move(n-1, B,A,C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "\n",
    "        def move(n,A,B,C):\n",
    "            if n <= 0:\n",
    "                return\n",
    "            move(n-1,A,C,B)\n",
    "            C.append(A[-1])\n",
    "            A.pop()\n",
    "            move(n-1,B,A,C)\n",
    "\n",
    "        move(n,A,B,C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        def hanoi(n, A, B, C):\n",
    "            if n == 1:\n",
    "                C.append(A[-1])\n",
    "                A.pop()\n",
    "            else:\n",
    "                hanoi(n-1, A, C, B)\n",
    "                C.append(A[-1])\n",
    "                A.pop()\n",
    "                hanoi(n-1, B, A, C)\n",
    "        n = len(A)\n",
    "        hanoi(n, A, B, C)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        def h(n,A,B,C):\n",
    "            if n==1:\n",
    "                C.append(A.pop())\n",
    "                return\n",
    "            else:\n",
    "                h(n-1,A,C,B)\n",
    "                C.append(A.pop())\n",
    "                h(n-1,B,A,C)\n",
    "        return h(len(A),A,B,C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        def move(n,a,b,c):\n",
    "            if n == 1:\n",
    "                c.append(a.pop())\n",
    "                return\n",
    "            else:\n",
    "                move(n-1,a,c,b)\n",
    "                c.append(a[-1])\n",
    "                a.pop()\n",
    "                move(n-1,b,a,c)\n",
    "        move(n,A,B,C)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        d = len(A)\n",
    "\n",
    "\n",
    "        def one_step(n, a, b, c):\n",
    "            if n == 0:\n",
    "                return\n",
    "            else:\n",
    "                one_step(n - 1, a, c, b)\n",
    "                c.append(a.pop())\n",
    "                one_step(n - 1, b, a, c)\n",
    "\n",
    "            \n",
    "        one_step(d, A, B, C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        self.move(len(A), A, B, C)\n",
    "        \n",
    "    def move(self, n: int, src: List[int], tmp: List[int], dst: List[int]) -> None:\n",
    "        if n <= 0:\n",
    "            return\n",
    "        self.move(n - 1, src, dst, tmp)\n",
    "        dst.append(src.pop(len(src) - 1))\n",
    "        self.move(n - 1, tmp, src, dst)\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        def move(n, A, B, C):\n",
    "            if n == 0: return\n",
    "            B = A[1:]\n",
    "            C.append(A[0])\n",
    "            move (n-1, B, A, C)\n",
    "        \n",
    "        move(n, A, B, C)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify C in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        \n",
    "        def move(n,A,B,C):\n",
    "            if n == 1:\n",
    "                C.append(A[-1])\n",
    "                A.pop()\n",
    "                return\n",
    "            else:\n",
    "                move(n-1,A,C,B)\n",
    "                C.append(A[-1])\n",
    "                A.pop()\n",
    "                move(n-1,B,A,C)\n",
    "        move(n,A,B,C)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
